/**
 * Recife Action Tools - RAT
 * Centro de Inform�tica - CIn - UFPE
 *
 * Biblioteca para Gera��o de Parser
 */
package br.ufpe.abaco.ParserGen.parser;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.io.Serializable;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Stack;
import java.util.Vector;

/**
 *  Tabelas de parsing para um parser LR. Inclui as tabelas: actionsTable (acoes
 *  sintaticas) e goto (desvios).
 *
 *@author     Monique Monteiro e Pablo Sampaio
 *@created    30 de Outubro de 2002
 */
public class LRTable implements Serializable {
	//static int FIRST_STATE = 0;
	/**
	 * Mapeia objetos TerminalSymbol em um array bidimensional de acoes
	 * sintaticas (Action). Cada linha desse array contem as acoes de um estado
	 * especifico. O uso deve ser: actionsTable[TerminalSymbol.index][estado] =>
	 * o "resultado" eh um array de acoes.
	 */
	private LRState states[];
	private ParserAction[][] actionsTable;
	/**
	 * Mapeia objetos NonTerminalSymbol em um array de inteiros (representando
	 * os estados). Uso: gotoTable[NonTerminalSymbol.index][estado] => proximo
	 * estado.
	 */
	private int[][] gotoTable;
	private BNFGrammar grammar;
	//dados para debug
	private int numberOfStates;
	private boolean debug;
	private StringBuffer log = new StringBuffer();
	private static String TABLE_FILE = "TABELA.TXT";
	int ambiguities;
	public LRTable(BNFGrammar grammar, Vector<Production> start ) {
		this(grammar, start, false);
	}
	/**
	 * Construtor da tabela de parsing. Recebe a gram�tica aumentada e a
	 * producao inicial (gerada ao se "aumentar" a grammar).
	 */
	public LRTable(BNFGrammar grammar, Vector<Production> start, boolean debug) {
		this.debug = debug;
		this.grammar = grammar;
		HashMap collection = null;
		collection = this.canonicalCollection(start);
		
		this.fillActionTable(collection, start);
		this.fillGotoTable(collection);
	}
	/**
	 * Funcao de acoes sintaticas. Recebe o estado atual e um simbolo terminal e
	 * retorna a primeira acao sintatica que pode ser realizada pelo parser.
	 */
	ParserAction getActionEntry(int state, TerminalSymbol terminal) {
		return this.actionsTable[terminal.index][state];
	}
	/**
	 * Funcao de acoes sintaticas. Recebe o estado atual e um simbolo terminal e
	 * retorna as acoes sintaticas que podem ser realizadas pelo parser no array
	 * passado como parametro.
	 */
	ParserAction[] getActionEntry(int state, TerminalSymbol terminal,
			ParserAction[] array) {
		return this.actionsTable[terminal.index][state].toArray();
	}
	/**
	 * Funcao de desvio. Recebe o estado atual e um simbolo nao-terminal.
	 * Retorna o proximo estado. Retorna -1 no caso de um erro de parsing.
	 * 
	 * @param state
	 *            Description of the Parameter
	 * @param symbol
	 *            Description of the Parameter
	 * @return The gotoEntry value
	 */
	int getGotoEntry(int state, NonTerminalSymbol symbol) {
		return this.gotoTable[symbol.index][state];
	}
	/**
	 * Inicializa e preenche toda a tabela de acoes sintaticas.
	 * 
	 * @param collection
	 *            Description of the Parameter
	 * @param prodInicial
	 *            Description of the Parameter
	 */
	private void fillActionTable(Map<LRState,Integer> collection, Vector<Production> prodInicials) {
		Iterator itSets = collection.keySet().iterator();
		TerminalSymbol[] terminals = this.grammar.getTerminals();
		//desnecessario (pode usar so os indices)
		LRState estado;
		LRItem[] items;
		Production prod;
		int i;
		int stateNumber;
		this.createActionTable(collection.size());
		if (debug) {
			log
					.append("\n\n================ AMBIGUITIES LIST =================\n\n");
		}
		while (itSets.hasNext()) {
			estado = (LRState) itSets.next();
			items = estado.getItems();
			stateNumber = ((Integer) collection.get(estado)).intValue();
			for (i = 0; i < items.length; i++) {
				prod = items[i].production;
				//se o ponto estiver no fim da producao
				if (items[i].position == prod.getRightSide().length) {
					if (prodInicials.contains(prod)) {
						this.addAction(stateNumber, new AcceptAction());
					} else {
						ReduceAction reduce = new ReduceAction(prod, debug, log);
						addAction(stateNumber, terminals[0].index, reduce);
						for (int j = 1; j < terminals.length; j++) {
							int oldNumberOfActions = actionsTable[terminals[j].index][stateNumber]
									.getLength();
							actionsTable[terminals[j].index][stateNumber] = actionsTable[terminals[0].index][stateNumber];
							if (actionsTable[terminals[j].index][stateNumber]
									.getLength() > oldNumberOfActions) {
								//houve ambiguidade
								ambiguities++;
							}
						}
					}
				}
			}
			//se o ponto vier no inicio ou no meio da producao
			GrammarSymbol[] read = estado.getReadSymbols();
			int[] destPlaces = estado.destPlaces;
			for (i = 0; i < read.length; i++) {
				//se apos o ponto vier um simbolo terminal...
				if (read[i] instanceof TerminalSymbol) {
					int state = destPlaces[i];
					Production production = estado.getAssociatedProduction(i);
					addAction(stateNumber, read[i].index, new ShiftAction(
							state, production, debug, log));
				}
			}
		}
	}
	/**
	 * Inicializa a tabela de acoes sintaticas. Metodo auxiliar usado por
	 * fillActionTable().
	 */
	private void createActionTable(int estados) {
		ParserAction error = new ErrorAction();
		int numTerminals = this.grammar.getNumTerminals();
		this.actionsTable = new ParserAction[numTerminals][];
		for (int i = 0; i < numTerminals; i++) {
			ParserAction corr[] = new ParserAction[estados];
			actionsTable[i] = corr;
			for (int j = 0; j < estados; j++) {
				//todas as posicoes da tabela sao preenchidas com erro
				corr[j] = error;
			}
		}
	}
	/**
	 * Adiciona uma a��o do tipo ACCEPT � tabela de a�oes
	 * 
	 * @param state
	 *            o estado
	 */
	private void addAction(int state, AcceptAction newAction) {
		addAction(state, TerminalSymbol.EOF.index, newAction);
	}
	private void addAction(int state, int terminal, ParserAction newAction) {
		if (newAction == null) {
			throw new IllegalArgumentException("parametro newAction null!");
		}
		ParserAction oldActions = actionsTable[terminal][state];
		//Obt�m o s�mbolo lido
		TerminalSymbol symbol = this.grammar.getTerminals()[terminal];
		if (oldActions instanceof ErrorAction) {
			actionsTable[terminal][state] = newAction;
		} else if (!actionsTable[terminal][state].hasAction(newAction)) {
			//se a nova a��o j� n�o est� nesta entrada da tabela => TALVEZ ESTA
			// VERIFICACAO
			//NAO PRECISE SER FEITA!!!
			int oldNumberOfActions = actionsTable[terminal][state].getLength();
			actionsTable[terminal][state] = actionsTable[terminal][state]
					.addAction(state, symbol, newAction);
			//newAction.nextAction = actionsTable[terminal][state];
			//newAction.length = actionsTable[terminal][state].length+1;
			//actionsTable[terminal][state] = newAction;
			if (actionsTable[terminal][state].getLength() > oldNumberOfActions) {
				//houve ambiguidade
				ambiguities++;
			}
		}
	}
	/**
	 * Inicializa e preenche toda a tabela de desvios.
	 */
	private void fillGotoTable(Map collection) {
		NonTerminalSymbol[] nonTerminals = this.grammar.getNonTerminals();
		Iterator itStates = collection.keySet().iterator();
		LRState atual;
		LRState proximo;
		int numAtual;
		int numProximo;
		int i;
		int collectionSize = collection.size();
		this.gotoTable = new int[nonTerminals.length][];
		for (i = 0; i < this.gotoTable.length; i++) {
			gotoTable[i] = new int[collectionSize];
		}
		while (itStates.hasNext()) {
			atual = (LRState) itStates.next();
			numAtual = ((Integer) collection.get(atual)).intValue();
			GrammarSymbol[] read = atual.getReadSymbols();
			int[] destPlaces = atual.destPlaces;
			for (i = 0; i < read.length; i++) {
				if (read[i] instanceof NonTerminalSymbol) {
					this.gotoTable[read[i].index][numAtual] = destPlaces[i];
				}
			}
		}
	}
	/**
	 * Constroi a colecao canonica de conjuntos de itens na forma de um
	 * mapeamento de LRState em indices (a serem usados para representar os
	 * estados).
	 */
	private HashMap<LRState,Integer> canonicalCollection(Vector<Production> startProds) {
		HashMap<LRState,Integer> collection = new HashMap<LRState,Integer>();
		Stack<LRState> naoCalculados = new Stack<LRState>();
		LRState desvio;
		LRState atual;
		GrammarSymbol[] simbolos = this.grammar.getSymbols();
		int i;
		int nextIndex = 0;
		if (debug) {
			log
					.append("\n\n================ STATES & CANONICAL COLLECTION =================\n\n");
		}
		for (Production startProd : startProds) {
			atual = new LRState();
			atual.addItem(startProd.items[0]);
			if (debug) {
				log.append("State "+nextIndex+": \n\n" + atual.toString() + "\n\n\n");
			}
			collection.put(atual, new Integer(nextIndex++));
			naoCalculados.push(atual);
		}
		desvio = new LRState();
		do {
			atual = (LRState) naoCalculados.pop();
			GrammarSymbol read[] = atual.getReadSymbols();
			int destPlaces[] = new int[read.length];
			for (i = 0; i < read.length; i++) {
				desvio.clear();
				atual.branch(read[i], desvio);
				Object dest = collection.get(desvio);
				if (dest == null) {
					LRState novo = desvio.getCopy();
					naoCalculados.push(novo);
					destPlaces[i] = nextIndex;
					collection.put(novo, new Integer(nextIndex));
					if (debug) {
						log.append("State " + nextIndex + "\n\n"
								+ novo.toString() + "\n\n\n");
					}
					nextIndex++;
				} else {
					destPlaces[i] = ((Integer) dest).intValue();
				}
			}
			atual.destPlaces = destPlaces;
		} while (!naoCalculados.empty());
		numberOfStates = nextIndex;
		return collection;
	}
	public void print() {
		try {
			PrintWriter pw = new PrintWriter(new FileOutputStream(TABLE_FILE));
			int n_estados = this.actionsTable[0].length;
			TerminalSymbol[] terminals = this.grammar.getTerminals();
			int curr_state;
			int curr_symbol;
			for (curr_state = 0; curr_state < n_estados; curr_state++) {
				pw.println("State: " + curr_state);
				pw.println(states[curr_state]);
				pw.println("\n\n");
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	/**
	 * Retorna a gram�tica, o n�mero de estados, os conjuntos de itens, o n�mero
	 * e a lista de ambiguidades.
	 */
	public String getLog() {
		String result = "\n\n================ LANGUAGE'S GRAMMAR =================\n\n"
				+ grammar.toString()
				+ "\n\n"
				+ "Number of states = "
				+ numberOfStates
				+ "\n\n"
				+ "Number of ambiguities = "
				+ ambiguities + "\n\n" + log.toString();
		return result;
	}
}
/**
 * Esta classes representa as a��es sint�ticas contidas na tabela. De fato, �
 * uma lista ligada que cont�m as a��es em uma entrada da tabela de a��es.
 */
abstract class ParserAction implements Serializable {
	protected Production production;
    int length = 1;
	public ParserAction nextAction;
	private boolean debug;
	private StringBuffer log;
	/**
	 * Construtor default da classe.
	 *  
	 */
	ParserAction() {
	}
	/**
	 * Construtor da classe.
	 * 
	 * @param production
	 *            a produ��o � qual a a��o se parsing est� relacionada.
	 */
	ParserAction(Production production) {
		this.production = production;
	}
	/**
	 * Construtor da classe.
	 * 
	 * @param production
	 *            a produ��o � qual a a��o se parsing est� relacionada.
	 */
	ParserAction(Production production, boolean debug, StringBuffer log) {
		this.production = production;
		this.debug = debug;
		this.log = log;
	}
	/**
	 * Retorna o tamanho da lista de a��es.
	 * 
	 * @return int
	 */
	public int getLength() {
		return length;
	}
	/**
	 * Retorna <code>true</code> se uma dada a��o j� existe na posi��o
	 * corrente da tabela ou <code>false</code> caso contr�rio.
	 * 
	 * @param action
	 *            a a��o a ser procurada.
	 * @return <code>boolean</code>
	 */
	public boolean hasAction(ParserAction action) {
		boolean result = false;
		for (ParserAction aux = this; aux != null; aux = aux.nextAction) {
			if (aux.equals(action)) {
				result = true;
				break;
			}
		}
		return result;
	}
	public ParserAction[] toArray() {
		ParserAction[] result = new ParserAction[length];
		ParserAction aux = this;
		for (int i = length - 1; i >= 0; i--) {
			result[i] = aux;
			aux = aux.nextAction;
		}
		return result;
	}
	/*
	 * public ParserAction[] toArray(ParserAction[] array) { if(array == null){
	 * throw new IllegalArgumentException("parametro null"); }
	 * 
	 * if (array.length != length) { //cria um novo array array = new
	 * ParserAction[length]; }
	 * 
	 * ParserAction aux = this;
	 * 
	 * for (int i = length - 1; i >= 0; i--) { array[i] = aux; aux =
	 * aux.nextAction; }
	 * 
	 * return array;
	 *  }
	 */
	/**
	 * Adiciona uma a��o de parsing. Se a nova a��o tiver preced�ncia igual a
	 * esta a��o, � adicionada normalmente, de forma que a nova a��o passa a
	 * apontar para esta a��o e torna-se a "cabe�a da lista", sendo retornada.
	 * Se a nova a��o tiver preced�ncia maior do que esta a��o, e
	 * conseq�entemente maior do que todas as pr�ximas a��es (por indu��o),
	 * passa a ocupar sozinha a lista, sendo retornada. Se a nova a��o tiver
	 * preced�ncia MENOR do que esta a��o, n�o � inserida na lista e esta a��o �
	 * que � retornada.
	 * 
	 * @param state
	 *            o estado (usado apenas para informa��es de log).
	 * @param symbol
	 *            o terminal lido (usado apenas para informa��es de log).
	 * @param newAction
	 *            a a��o que se deseja inserir na lista.
	 * @return ParserAction a a��o adicionada
	 * @throws ParserGenerationException
	 *             se a produ��o associada � a��o passada como par�metro for n�o
	 *             associativa e houver conflito shift-reduce com uma a��o que
	 *             esteja associada � mesma produ��o.
	 */
	ParserAction addAction(int state, TerminalSymbol symbol,
			ParserAction newAction) {
		ParserAction result = null;
		int oldPrecedence = this.getPrecedence();
		int newPrecedence = newAction.getPrecedence();
		if (newPrecedence > oldPrecedence) {
			result = newAction;
		} else if (newPrecedence < oldPrecedence) {
			result = this;
		} else {
			if (debug && log != null) {
				log.append("<<CONFLICT>>\n");
				log.append("State: " + state + '\n');
				log.append("Symbol: " + symbol.name + '\n');
				log.append("Previous action: " + this + ", Rule: "
						+ this.production + '\n');
				log.append("New action: " + newAction + " Rule: "
						+ newAction.production + '\n');
				log.append("Previous actions's precedence = " + oldPrecedence
						+ '\n');
				log
						.append("New actions's precedence = " + newPrecedence
								+ '\n');
				log.append("It is not possible to solve the ambiguity.\n\n");
			}
			if (newAction.production.getAssociativity() == Production.NON_ASSOCIATIVE) {
				ParserAction action = findActionWithProduction(newAction.production);
				if ((newAction instanceof ShiftAction && action instanceof ReduceAction)
						|| (newAction instanceof ReduceAction && action instanceof ShiftAction)) {
					String errorMessage = "Shift-Reduce conflict envolving non-associative production "
							+ newAction.production.toString()
							+ " between the actions "
							+ newAction.print()
							+ " and " + action.print();
					if (debug && log != null) {
						log.append(errorMessage);
					}
					throw new ParserGenerationException(errorMessage);
				}
			}
			newAction.nextAction = this;
			newAction.length = length + 1;
			result = newAction;
		}
		return result;
	}
	/**
	 * Retorna a pr�xima a��o.
	 * 
	 * @return ParserAction
	 */
	ParserAction getNextAction() {
		return nextAction;
	}
	/**
	 * Retorna uma a��o que esteja associada � prodcu��o passada como par�metro,
	 * e <code>null</code> caso esta a��o n�o exista.
	 * 
	 * @param production
	 *            a produ��o procurada
	 * @return ParserAction
	 */
	private ParserAction findActionWithProduction(Production production) {
		ParserAction aux;
		for (aux = this; aux != null; aux = aux.nextAction) {
			if (aux.production.equals(production)) {
				break;
			}
		}
		return aux;
	}
	public abstract boolean equals(Object o);
	public abstract String print();
	public abstract String toString();
	/**
	 * Retorna a preced�ncia desta a��o. Se for uma a��o de shift, retorna a
	 * preced�ncia de shift da produ��o associada. Se for uma a��o de reduce,
	 * retorna a preced�ncia de reduce da produ��o associada. Se for uma a��o de
	 * erro, retorna uma preced�ncia m�nima, e se for uma a��o de aceita��o,
	 * retorna uma preced�ncia m�xima.
	 * 
	 * @return int
	 */
	public abstract int getPrecedence();
}
class ReduceAction extends ParserAction {
	ReduceAction(Production production) {
		super(production);
	}
	ReduceAction(Production production, boolean debug, StringBuffer log) {
		super(production, debug, log);
	}
	public boolean equals(Object o) {
		if (o != null && o instanceof ReduceAction) {
			return this.production == ((ReduceAction) o).production;
		} else {
			return false;
		}
	}
	public int getPrecedence() {
		return this.production.getReducePrecedence();
	}
	public String print() {
		return "reduce [ " + this.production + " ]";
	}
	public String toString() {
		return "r" + this.production.index;
	}
}
class ShiftAction extends ParserAction {
	final int state;
	ShiftAction(int state, Production production) {
		super(production);
		this.state = state;
	}
	ShiftAction(int state, Production production, boolean debug,
			StringBuffer log) {
		super(production, debug, log);
		this.state = state;
	}
	public boolean equals(Object o) {
		if (o != null && o instanceof ShiftAction) {
			return this.state == ((ShiftAction) o).state;
		} else {
			return false;
		}
	}
	public int getPrecedence() {
		return this.production.getShiftPrecedence();
	}
	public String print() {
		return "shift " + this.state + " " + this.production;
	}
	public String toString() {
		return "s" + this.state;
	}
}
class AcceptAction extends ParserAction {
	public AcceptAction() {
	}
	public boolean equals(Object o) {
		return (o != null && o instanceof AcceptAction);
	}
	public int getPrecedence() {
		return Integer.MAX_VALUE;
	}
	public String print() {
		return "accept";
	}
	public String toString() {
		return "acc";
	}
}
class ErrorAction extends ParserAction {
	public ErrorAction() {
	}
	public boolean equals(Object o) {
		return (o != null && o instanceof ErrorAction);
	}
	public int getPrecedence() {
		return Integer.MIN_VALUE;
	}
	public String print() {
		return "error";
	}
	public String toString() {
		return "err";
	}
}